#!/usr/bin/python
from random import uniform
def find_xIndex(x, array):
	i = 0
	for value in array:
		if x < value:
			return i
		i += 1
	return 0

func = lambda x:x**2.
weight = lambda x:x**1.

x = [.001*(i+1.) for i in range(1000)]
# create the weight prob. boundary and name as norm_w
weightList = [weight(i) for i in x]
sum_w = sum(weightList)
norm_w = []
t_sum = 0.0
for i in weightList:
	t_sum += i/sum_w
	norm_w.append(t_sum)

result = 0.0
result_w = 0.0
N_iter = 10000

# start calculate average
for i in range(N_iter):
	ran = uniform(0,1)
	x_index = find_xIndex(ran, norm_w)	
	result += func(x[x_index])/weight(x[x_index])
	result_w += 1/weight(x[x_index])

# normalized
avg = result/float(N_iter)
print avg
